We report the discovery of 70.5 ms pulsations from the X-ray source AX J1838.0-0655 using the Rossi X-ray Timing Explorer (RXTE). PSR J1838-0655 is a rotation-powered pulsar with spin-down luminosity Edot = 5.5e36 ergs/s, characteristic age tau = P/2Pdot = 23 kyr, and surface dipole magnetic field strength Bs = 1.9e12 G. It coincides with an unresolved INTEGRAL source and the extended TeV source HESS J1837-069. At an assumed distance of 6.6 kpc by association with an adjacent massive star cluster, the efficiency of PSR J1838-0655 converting spin-down luminosity to radiation is 0.8% for the 2-10 keV ASCA flux, 9% for the 20-300 keV INTEGRAL flux and ~3% for the >200 GeV emission of HESS J1837-069, making it a plausible power source for the latter. A Chandra X-ray observation resolves AX J1838.0-0655 into a bright point source surrounded by a ~2' diameter, centrally peaked nebula. The spectra of the pulsar and nebula are each well fitted by power laws, with photon indices Gamma = 0.5(0.3-0.7) and Gamma = 1.6(1.1-2.0), respectively. The 2-10 keV X-ray luminosities of the pulsar and nebula are L(PSR) = 4.6e34 d(6.6)^2 ergs/s and L(PWN) = 5.2e33 d(6.6)^2 ergs/s. A second X-ray source adjacent to the TeV emission, AX J1837.3-0652, is resolved into an apparent pulsar/PWN; it may also contribute to HESS J1837-069. The star cluster RSGC1 may have given birth to one or both pulsars, while fueling TeV emission from the extended PWN with target photons for inverse Compton scattering.